package sort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GuiBinSort {

	public static void main(String[] args) {
		Map<Integer, String> map = new HashMap<Integer, String>();
		int[] a = { 5, 2, 9, 3, 10, 1, 15, 2, 6, 7, 19, 50, 69, 100, 150, 160,
				132, 169 };
		ArrayList<Integer> list = new ArrayList<>(map.keySet());
		list.toArray();
		mergeSort(a);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

	public static List<String> clear(ArrayList<String> array) {
		Map<Integer, String> map = new HashMap<Integer, String>();

		Set<String> set = new HashSet<String>(array);
		ArrayList<String> list = new ArrayList<>(set);
		return list;
	}

	public static void mergeSort(int[] t) {
		if (t == null || t.length <= 1)
			return;
		int len = 1;
		// 程序边界的处理非常重要
		while (len <= t.length) {
			for (int i = 0; i + len <= t.length - 1; i += len * 2) {
				int low = i, mid = i + len - 1, high = i + len * 2 - 1;
				if (high > t.length - 1){
					high = t.length - 1;
				}
				merge(t, low, mid, high);
			}
			len *= 2;
		}
	}

	// 对数组nums作归并递归排序
	public static void merge(int[] nums, int low, int mid, int high) {
		int[] temp = new int[high - low + 1];
		int i = low;// 左指针
		int j = mid + 1;// 右指针
		int k = 0;
		// 把较小的数先移到新数组中
		while (i <= mid && j <= high) {
			if (nums[i] < nums[j]) {
				temp[k++] = nums[i++];
			} else {
				temp[k++] = nums[j++];
			}
		}
		// 把左边剩余的数移入数组
		while (i <= mid) {
			temp[k++] = nums[i++];
		}
		// 把右边边剩余的数移入数组
		while (j <= high) {
			temp[k++] = nums[j++];
		}

		// 把新数组中的数覆盖nums数组
		for (int k2 = 0; k2 < temp.length; k2++) {
			nums[k2 + low] = temp[k2];
		}
	}

	public static void merge(int[] c, int[] a, int[] b, int n, int m) {
		int i, j, k;
		for (i = 0, j = 0, k = 0; k < n + m; k++) {
			if (i == n) {
				c[k] = b[j];
				j++;
				continue;
			}
			if (j == m) {
				c[k] = b[i];
				i++;
				continue;
			}
			c[k] = a[i] < b[j] ? a[i++] : b[j++];
		}
	}

	public void mergeSort(int[] a, int left, int right) {
		int i, m;
		// 每次的序列长度加倍
		for (m = 1; m <= right - left; m += m) {
			for (i = left; i <= left - m; i += m + m) {

			}
		}
	}
}
